
%!TEX root = main.tex

\section{CubeTA algorithm}\label{sec:qp}

%Given a query, for each keyword, we access the 3d lists in order based on their relevancy to the keyword.

%For time, we can identify the latest time slice. For frequency, we can first identify the largest frequency. But for social, add the following}


%\reminder{\subsection{Social Ordering} this should be a subsection. it is very small}


%\reminder{Social Order}. Since the social relevancy of different partitions to the query depends on the online query, thus the partitions cannot be sorted offline. To get a sorted social order, we will rank the social partitions $P_i$ by $\textbf{SD}(P_v,P_i)$. Obviously, the partition $P_v$ which contains the query user $v$ should be first accessed.

%Recall from section \ref{sec:Index}, the social dimension does not have ordering before processing any query. But without ordering on social dimension we cannot effectively use the 3D lists to retrieve top-k results. The social partition will only be ordered whenever a user $v$ submits a query and therefore the ordering is computed during query time. The partition ranking uses the pre-computed distances between any pair of partitions that described in \ref{sec:Index} to approximate the distance between $v$ to any partition.

%When a user $v$ submits a query $q=\langle q.v,q.W,q.t,q.k \rangle$ to the system, the pre-processing step extracts all the keywords and their inverted lists. Then the social partition which contains $v$ will be identified.For each extracted keyword $u$, we need to compute lower bound of the shortest distance from $v$ to the sub-partition with respect to $u$ using the distance look up table. Since $v$ belongs to partition $P_v$, estimating the lower bound distance from $v$ to a sub partition $P' \in P_i, i = 1,2,...,c$ would be obvious because we can make use of the shortest distance from $P_v$ to $P_i$. However, this lower bound would be inaccurate as it does not consider the keyword information.

%Let us focus on estimating the social distance with respect to a keyword $u$ for an example. To calculate the distance between user $v$ and the sub partition $P'$ where $P' \in P_j$ and each $u \in P'$ has published a document that contains $u$, we retrieve $d_{min} = \textbf{SD}_{min}(u_j,pn_j)$ and $d_{max} = \textbf{SD}_{max}(u_j,pn_j)$ from $u$'s distance lookup table illustrated by Table \ref{tab:ClusterKeywordDis}. Let $\textbf{SD}(v,P')=\min_{u \in P'}{\textbf{SD}(v,u)}$,

%\begin{equation}\label{eq:DistBound}
%\textbf{SD}(v,P') \geq %\max(\textbf{SD}(v,pn_j)-d_{max},d_{min}-\textbf{SD}(v,pn_j),\textbf{SD}(P_v,P_j))
%\end{equation}

\begin{algorithm}[t] % ---------------------------------Algo 1
\caption{\textbf{CubeTA Algorithm}}
\label{algo:cubeTA}
\KwIn{Query $q = \langle q.v,q.W,q.t,q.k \rangle$, CubeQueue $CQ$ which is initialized by inserting the first cube for each of the $q.W$'s inverted list.}
\KwOut{Top $q.k$ records that match the query $q$.}

MinHeap $H \gets \phi$ \tcc*[f]{$q.k$ best records} \\
$\varepsilon \gets 0$ \tcc*[f]{$q.k^{th}$ record's score}\\

\While{$!CQ.empty()$}{
    Cube $cb = CQ.pop()$ \\
    \If{$\textbf{EstimateBestScore}(q,cb) < \varepsilon$}{  \label{line:stoprule}
        \Return $H$
    }
    \Else{
        \ForEach{record $r$ in $cb$}{
            \If{$r$ has not been seen before}{
                \If{$\textbf{GetActualScore}(q,r,\varepsilon) > \varepsilon$}{
                    $H.pop()$ and Push $r$ to $H$ \\
                    $\varepsilon \gets H.top()$'s score w.r.t $q$
                }
            }
        }
        \ForEach{of the three neighbour cubes $nc$ of $cb$}{
            \If{$nc$ has not been seen before}{
                \If{$\textbf{EstimateBestScore}(q,cb) > \varepsilon$}{
                    Push $nc$ to CQ \\
                }
            }
        }
    }
}
\end{algorithm}

%\noindent\textbf{Cube-based TA algorithm (CubeTA)}

Given the 3D list design, we are now ready to present our basic query evaluation scheme, CubeTA (Algorithm \ref{algo:cubeTA}).
%The original TA algorithm \cite{TA:Fagin:POS:2001} provides efficient pruning for the candidate records.
CubeTA extends the famous TA algorithm \cite{TA:Fagin:POS:2001} by introducing a two-level pruning upon the 3D list to further speed up the query processing, i.e. at record level and at cube-level.
We maintain two data structures in CubeTA: (1) The cube queue $CQ$ which ranks the cubes by their estimated relevance scores (computed by \textbf{EstimateBestScore} function in line 15); (2) the min heap $H$ which maintains the current top-k candidates.
The main workflow is as follows: In each iteration, we first access
the 3D list for each keyword and get the cube $cb$ with the best estimated scores among all unseen cubes in $CQ$ (line 4).
Next we evaluate all the records stored in $cb$ (lines 8-12),
then we keep expanding the search to the three neighbors of $cb$ (lines 13-16), until the current top-k records are more relevant than the next best unseen cube in $CQ$.
Following Equation \ref{eq:RankingFunction} in computing the score of a record, Equation \ref{eq:ApproxCube} illustrates how \textbf{EstimateBestScore} estimates the score of a cube $cb$:


\vspace{-3mm}
\begin{equation}
\Re(q,cb) = |q.W|({\alpha}\textbf{TS}_{cb} + \frac{{\beta}\textbf{SR}_{cb} + {\gamma}\textbf{TF}_{cb}}{|q.W|})
\label{eq:ApproxCube}
\end{equation}
\vspace{-3mm}

\noindent The social score of $cb$ is $\textbf{SR}_{cb}=1-\textbf{SD}(P_{q.v},P_{cb})$, where $P_{q.v}$ is the partition containing the query user and $P_{cb}$ is the partition containing the cube $cb$. The time freshness $\textbf{TF}_{cb}$ and text similarity $\textbf{TS}_{cb}$ are
the maximum values of $cb$'s time interval and frequency interval.
%
It is easy to see that the total estimated score $\textbf{SR}_{cb}$ is actually an upper bound of all the unseen records in the cube, so if it is still smaller than the current $k^{th}$ best record's score $\varepsilon$,
we can simply terminate the search and conclude the top-k results are found
(lines 5-6). This stopping condition is presented in
Theorem \ref{thm:upperbound}.
%so that the stopping criterion in Line \ref{line:stoprule} of Algorithm \ref{algo:cubeTA} is correct.

\begin{theorem}\label{thm:upperbound}
Let $\mathbf{cb}$ be the next cube popped from $CQ$. The score estimated by Equation \ref{eq:ApproxCube} is the upper bound of any unseen record in the 3D lists of all query keywords $q.W$.
\end{theorem}

\noindent
\textit{Proof}:
%From Equation \ref{eq:RankingFunction}, we derive Equation \ref{eq:ApproxCube}.
Let $r$ be any record that exists in any of the 3D lists and whose score has not been computed. Given a query $q$, let $\Delta=\beta \textbf{SR}(q.v,r.v) + \gamma \textbf{TF}(q.t,r.t)$ and $\delta_w=\alpha \cdot tf_{w,r} \cdot idf_w$ where $w \in q.W$. The overall score $\Re(q,r_x)$ of $r$ w.r.t. $q$ is:

\vspace{-5mm}
\begin{align}
\Re(q,r_x) &= \Delta + \sum_{w \in q.W} \delta_w = \sum_{w \in q.W}(\delta_w + \frac{\Delta}{|q.W|}) \nonumber \\\vspace{-2mm}
&= \hspace{-6mm} \sum_{w \in q.W \cap r.W} \hspace{-6mm}(\delta_w + \frac{\Delta}{|q.W|}) + \frac{\Delta|q.W \setminus r_x.W|}{|q.W|} \label{eq:multikey}
\end{align}
\vspace{-2mm}

%\vspace{-4mm}
%\begin{align}
%\Re(q,r_x) &= {\alpha}(\Sigma_{w \in q.W} tf_{w,r_x} \cdot idf_w) + {\beta}\mathbf{SR} + {\gamma}\mathbf{TF} \nonumber \\\vspace{-2mm}
%&= \Sigma_{w \in q.W}(\alpha tf_{w,r_x} \cdot idf_w + \frac{{\beta}\mathbf{SR}+\gamma\mathbf{TF}}{|q.W|}) \nonumber \\\vspace{-2mm}
%&= \Sigma_{w \in q.W \cap r_x.W}{(\alpha tf_{w,r_x} \cdot idf_w + \frac{{\beta}\mathbf{SR}+{\gamma}\mathbf{TF}}{|q.W|})} \nonumber \\\vspace{-6mm}
%&+ |q.W \setminus r_x.W|(\frac{{\beta}\mathbf{SR}+{\gamma}\mathbf{TF}}{|q.W|}) \label{eq:multikey}
%\end{align}
%\vspace{-4mm}

\noindent But note that $r_x$ must exist in one of the 3D lists, say $w^{*}$. Then it follows Equation \ref{eq:multikey}:

\vspace{-5mm}
\begin{align}
\Re(q,r_x) &\leq \hspace{-6mm} \sum_{w \in q.W \cap r.W} \hspace{-6mm} (\delta_w + \frac{\Delta}{|q.W|}) +
|q.W \setminus r_x.W|(\delta_{w^{*}} + \frac{\Delta}{|q.W|}) \nonumber \\
\vspace{-8mm}
&\leq |q.W| \cdot \max_{cb \in q.W}(\alpha\mathbf{TS}_{cb} + \frac{{\beta}\mathbf{SR}_{cb}+{\gamma}\mathbf{TF}_{cb}}{|q.W|}) \nonumber \rlap{$\hspace{0.5cm} \blacksquare$}
\end{align}
\vspace{-2mm}


\begin{algorithm}[htp] % ---------------------------------Algo 3
\caption{\textbf{GetActualScore Algorithm}}
\label{algo:ComputeExactScore}
\KwIn{Query $q$, record $r$ and threshold $\varepsilon$}
\KwOut{$\Re(q,r) > \varepsilon$ ? $\Re(q,r)$ : $-1$}

Compute $\textbf{TF}$ and $\textbf{TS}$ using the forward list of $r$ \\
Compute the Social Relevance Lower Bound $\min{\textbf{SR}_r} = (\varepsilon - \alpha\textbf{TS} - \gamma\textbf{TF})/ \beta$
\label{line:diststop} \\
$\textbf{SR}_r = 1-\textbf{ShortestDistance}(q.v, r.v, \min{\textbf{SR}_r})$ \\
\Return $\alpha\textbf{TF} + \beta\textbf{TS} + \gamma\textbf{SR}$
\end{algorithm}
%\reminder{you do not discuss how to compute accurate social relevancy here? no need? or refer to the next section?}

\textbf{GetActualScore} (Algorithm \ref{algo:ComputeExactScore}) computes the exact relevance of a certain record.
%time freshness is a direct computation by the publish time of the record.
With the forward list mentioned in Sec. \ref{sec:Index}, we can compute the exact text similarity and time freshness.
%Lastly the social distance from the query user to the user who post the record will be computed. Note that we will evaluate time freshness and text similarity first.
Since we have the $k^{th}$ best score $\varepsilon$ among the evaluated records, a lower bound for social relevance (i.e. the distance upper bound) can be computed for the current record $r$ before evaluating the distance query (in line 3).
%\ref{line:diststop} of Algorithm \ref{algo:ComputeExactScore}.
This bound enables efficient pruning which we will later discuss on how to compute the exact social relevance score in Section \ref{sec:ShortestPath}. Example \ref{exmp:cubeTA} shows a running example of how CubeTA works.

%\vspace{-2mm}
%\begin{figure}[htp]
%    \centering
%        \includegraphics[width=0.5\textwidth]{pics/reordered_index}
%    \vspace{-5mm}\caption{Reordered inverted list of \quotes{icde}}
%    \label{fig:reordered_inverted_index}
%\end{figure}
%\vspace{-3mm}


\begin{figure}[htp]
    \centering
        \includegraphics[width=0.5\textwidth]{pics/cubeTAexample}
    \caption{Example of CubeTA (The highlighted text indicates that the records are being evaluated in their current iteration.)}
    \label{fig:cubeTAexample}
\end{figure}
\vspace{-3mm}

\begin{example}\label{exmp:cubeTA}
By Example \ref{exmp:rankmodel}, the social partitions are sorted by their distances to $u_1$ when $u_1$ issues the query. Fig. \ref{fig:text_3D_inverted} shows the reordered 3D list of keyword \quotes{icde}.
Detailed steps for CubeTA are illustrated in Fig. \ref{fig:cubeTAexample}. In iteration $1$, cube $cb(1,2,2)$ is first evaluated. Since no record is in $cb(1,2,2)$, three neighbors of $cb(1,2,2)$ are inserted into the cube queue.
In iteration $2$, $cb(1,1,2)$ is popped from the cube queue and before expanding its neighbor cubes into the queue, we evaluate $r7$ and insert it into the candidate max heap. This procedure terminates at iteration 5 because $r11$ is found
to have an equal score to the best cube score in the cube queue.
\end{example}




%\subsection{Efficient Cube Traversal}\label{sec:empty_cube}
\noindent\textbf{Efficient Cube Traversal}\\
As discussed in Sec. \ref{sec:Index}, traversing the 3D list may
encounter many empty cubes. To speed up the traversal in CubeTA (line 13), we define the boosting neighbors for a cube $cb(x,y,z)$:

\begin{defn}
Suppose there are $c$ social partitions and $m$ frequency intervals, the boosting neighbors of $cb(x,y,z)$ are:
\begin{itemize}
\item $cb(x-1,y,z)$ if $y=c \wedge z=m$.
\item $cb(x,y-1,z)$ if $z=m$.
\item $cb(x,y,max{\{ z'| z' < z \wedge cb(x,y,z') \text{ is non-empty} \}})$
\end{itemize}
\end{defn}

Boosting neighbors essentially can identify all the non-empty cubes, as illustrated below.
\begin{theorem}\label{theorem:boost_neighbours}
All cubes are covered by traversing via boosting neighbors only.
\end{theorem}

\vspace{-2mm}
\noindent
\textit{Proof}:
Let $l=max(x)$. As the traversal always starts from $cb(l,c,m)$, we need to prove that any $cb(x,y,z)$ is reachable from $cb(l,c,m)$. Along the textual dimension, $cb(x,y,z)$ is reachable from $cb(x,y,m)$. $cb(x,y,m)$ is reachable from $cb(x,c,m)$ along the social dimension. Lastly $cb(x,c,m)$ is reachable by $cb(l,c,m)$ along the time dimension. $\hspace{1cm} \blacksquare$
